//
// Created by sjjmw on 1/20/2022.
//
#include "base.h"

class Solution {
public:
    int fib(int n) {
        if(n<=1){
            return n;
        }
        //1.dp数组每一个数列的值，长度为n+1 例如2 ([0 1] 2)
        vector<int> dp(n+1);
        //3.初始化
        dp[0]=0;
        dp[1]=1;
        //4.遍历顺序
        for(int i=2;i<n+1;i++){
            //2.转移方程
            dp[i]=dp[i-1]+dp[i-2];
        }
        return dp[n];
    }
};